"""
难度：中等
一条包含字母 A-Z 的消息通过以下映射进行了 编码 ：
'A' -> 1
'B' -> 2
..
'Z' -> 26
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，"11106" 可以映射为：
"AAJF" ，将消息分组为 (1 1 10 6)
"KJF" ，将消息分组为 (11 10 6)
注意，消息不能分组为  (1 11 06) ，因为 "06" 不能映射为 "F" ，这是由于 "6" 和 "06" 在映射中并不等价。
给你一个只含数字的 非空 字符串 s ，请计算并返回 解码 方法的 总数 。
题目数据保证答案肯定是一个 32 位 的整数。
示例 1:
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
示例 2：
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
示例 3：
输入：s = "0"
输出：0
解释：没有字符映射到以 0 开头的数字。
含有 0 的有效映射是 'J' -> "10" 和 'T'-> "20" 。
由于没有字符，因此没有有效的方法对此进行解码，因为所有数字都需要映射。
示例 4：
输入：s = "06"
输出：0
解释："06" 不能映射到 "F" ，因为字符串含有前导 0（"6" 和 "06" 在映射中并不等价）。
提示：
1 <= s.length <= 100
s 只包含数字，并且可能包含前导零。
"""

"""
可用动态规划来做。设 dp[i] 表示字符串 s 前 i 个字符 s[0: i] 的翻译方案数。dp[i] 的来源有两种情况：
对 s[i] 进行翻译。那么只要 s[i] != 0，就可以被翻译为 A~I 的某个字母，此时方案数为 dp[i] = dp[i-1]
对 s[i-1] 和 s[i] 进行翻译，s[i-1] != 0，且 s[i-1] 和 s[i] 组成的整数必须小于等于 26 才能翻译，这样才能翻译为 J~Z 中的某字母，此时方案数为 dp[i] = dp[i-2]。
这两种情况有可能是同时存在的，也有可能都不存在。在进行转移的时候，将符合要求的方案数累加起来即可。
状态转移方程可以写为：
$dp[i] += \left{
，
\right.$
现在考虑初始边界条件。字符串为空时，只有一个翻译方案，翻译为空字符串，即 dp[0] = 1。
字符串只有一个字符时，需要考虑该字符是否为 0，不为 0 的话，dp[1] = 1，为 0 的话，dp[0] = 0。
字符串长度大于等于 2 时，就需要根据上边的状态转移方程来获取了，最终答案为 dp[n]。
"""
class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)
        dp = [0 for _ in range(n+1)]
        dp[0] = 1
        for i in range(1, n+1):
            if s[i-1] != '0':
                dp[i] += dp[i-1]
            if i > 1 and s[i-2] != '0' and int(s[i-2:i]) <= 26:
                dp[i] += dp[i-2]
        return dp[n]


        